/*
 * This is the first level tree structure of Range Tree.
 * It is inherited from RBTree.
 */

package MyTree;

import java.awt.Point;
import java.util.ArrayList;

import Red_Black_Tree.Node;
import Red_Black_Tree.RBTree;

public class MyTree extends RBTree {

	ArrayList<Node> allNodes = new ArrayList<Node>();
	
	public MyTree() {
		super();
		
		leaf = new MyNode();		
		leaf.setLeaf();
		leaf.setBlack();
	}
	
	/*
	 * Build associated structure for the first-level BST.
	 * For each node on this tree, call their "build associate tree" method.
	 */
	public void buildAssoTree(){
		traverseSubtree(root, allNodes);

		for(Node n : allNodes){
			MyNode n2 = (MyNode) n;
			n2.buildAssoTree();
		}
	}
	
	/*
	 * Traverse the subtree associated with current node,
	 * add them into the array.
	 */
	private void traverseSubtree(Node n, ArrayList<Node> array){
		if(!n.isLeaf()){
			array.add(n);
			traverseSubtree( n.getLChild(), array);
			traverseSubtree( n.getRChild(), array);
		}
	}
	
	public ArrayList<Point> query(int xmin, int xmax, int ymin, int ymax) {
		ArrayList<MyNode> leftPath = getPath(xmin);
		ArrayList<MyNode> rightPath = getPath(xmax);
		
		ArrayList<Point> report = new ArrayList<Point>();
		
		// find the split point
		// It is i-1 in the array
		int i = 0;
		for(i = 0; i < Math.min(leftPath.size(), rightPath.size()); i++){
			if(!leftPath.get(i).equals(rightPath.get(i))){
				break;
			}
		}
		
		// Test each of the two paths.  First xmin path
		for(MyNode n : leftPath){
			if (n.getX() >= xmin && n.getX() <= xmax && n.getY() >= ymin && n.getY() <= ymax) {
				//n.query_on_this_node(ymin, ymax);
				report.add(new Point(n.getX(), n.getY()));
			}
		}
		// Then xmax path
		for(int j = i; j < rightPath.size(); j++){
			int x = rightPath.get(j).getX();
			int y = rightPath.get(j).getY();
			if(x >= xmin && x <= xmax && y >= ymin && y <= ymax) {
				//rightPath.get(j).query_on_this_node(ymin, ymax);
				report.add(new Point(rightPath.get(j).getX(), rightPath.get(j).getY()));
			}
		}
		
		// Then report points between the two paths
		for(int j = i; j < leftPath.size(); j++){
			MyNode n = leftPath.get(j);
			if(xmin <= n.getX() && !n.getRChild().equals(leaf)){
				MyNode n2 = (MyNode) n.getRChild();
				n2.query(ymin, ymax, report);
			}
		}
		for(int j = i; j < rightPath.size(); j++){
			MyNode n = rightPath.get(j);
			if(xmax > n.getX() && !n.getLChild().equals(leaf)){
				MyNode n2 = (MyNode) n.getLChild();
				n2.query(ymin, ymax, report);
			}
		}

		return report;
	}
	
	public ArrayList<Point> query2(int xmin, int xmax, int ymin, int ymax) {
		ArrayList<Point> report = new ArrayList<Point>();
		
		for(Node n : allNodes){
			MyNode n2 = (MyNode) n;
			if(n2.getX() >= xmin && n2.getX() <= xmax && n2.getY() >= ymin && n2.getY() <= ymax)
				report.add(new Point(n2.getX(), n2.getY()));
		}
		
		return report;
	}
	

	private ArrayList<MyNode> getPath(int x) {
		ArrayList<MyNode> path = new ArrayList<MyNode>();	
		MyNode n = (MyNode) root;
		
		while (!n.isLeaf()) {
			path.add(n);
			
			if(x <= n.getX())
				n = (MyNode) n.getLChild();
			else
				n = (MyNode) n.getRChild();
		}
		
		return path;
	}

}
